LeetCode 581. Shortest Unsorted Continuous Subarray

581. Shortest Unsorted Continuous Subarray(最短无序连续子数组)

链接

https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray

题目

给定一个整数数组,你需要寻找一个连续的子数组,如果对这个子数组进行升序排序,那么整个数组都会变为升序排序。

你找到的子数组应是最短的,请输出它的长度。

示例 1:

输入: [2, 6, 4, 8, 10, 9, 15]
输出: 5
解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序,那么整个表都会变为升序排序。
说明 :

输入的数组长度范围在 [1, 10,000]。
输入的数组可能包含重复元素 ,所以升序的意思是<=。

思路

这题方法多种,可以排序之后对比,也可以用别的方法。
首先遍历,由前往后由后往前,分别确定两个边界。前向后时寻找右边界,每个数字判断是否小于前方最大值,若小于,就代表这个数需要排序,若大于,就代表这个数可以放在当前位置,若最后全为升序排列那就不用排序,后向前同理。
以输入示范,首先max为2,之后往后遍历,6>2,max=6,4<6,需要排序,一直往后,right=5,15大于前方所有数字,无需排序。反向遍历,2小于后方所有数,left=1,5-1+1=5.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int findUnsortedSubarray(int[] nums) {
int len = nums.length;
int max = nums[0];
int min = nums[len - 1];
int left = 0, right = -1;
for (int i = 0; i < len; i++) {
if (max > nums[i]) {
right = i;
} else {
max = nums[i];
}
}
for (int i = len - 1; i > -1; i--) {
if (min < nums[i]) {
left = i;
} else {
min = nums[i];
}
}
return right - left + 1;
}
---本文结束,感谢阅读---